The Story of a Lost Shinobi
by SimonRiley
Summary: Naruto has no idea where he is, when he is, or how he got there. Thrust into an unfamiliar world, he fruitlessly searches for a way home. In desperation, he seeks out the Avatar, hoping one of his past lives may have an answer for him.
1. Chapter 1

**A/N:** Naruto does not come from Canon Naruto in this story. He comes from a shinobi world very similar to Naruto Canon, but there are some fundamental differences that will be revealed over time. Don't worry about him being some broody emo Naruto though, I won't turn him into a Sasuke. This chapter will be short and introductory; You can expect following chapters to be much longer.

xxxxxxxxxx

"It is an honor to welcome you to the outer wall young avatar, but your help is not needed." Aang gave the general an incredulous look. "Not needed!"

"_Not_ needed." the general re-enunciated. "I assure you the situation is under control. The fire nation cannot penetrate this wall. Many have tried to break through it, but none have succeeded." He stated proudly.

Toph stole his thunder. "What about the Dragon of the West? He got in." The general visibly deflated.

"Well, technically yes, but he was _quickly_ expunged." He tried and failed to regain his bravado. "Nevertheless, that's why the city is called Ba Sing Se, It's the impenetrable city. They don't call it _Na_ Sing Se!" He briefly laughed at his own joke before deadpanning. "That means penetrable city."

Toph wasn't impressed. "Yeah, thanks for the tour, but we still got the drill problem."

"Not for long!" Declared General Sung cheerfully. "Young Master Uzumaki here is more than enough to take care of it." He gestured to a youth gazing passively at the drill.

He was wearing a black trench coat with red flames licking the bottom, along with a black and orange tracksuit underneath. A strange metal plate on a cloth was fastened to his forehead. He examined the gaang with piercing blue eyes before donning a cheerful smile. He strode up to Aang and extended his hand.

"Yo! Name's Naruto. Uzumaki Naruto. And you must be the Avatar! Nice to meet you."

Aang grabbed his hand with a similarly amicable look and gave it a shake. "Likewise. My name's Aang." He took a step back before rubbing the back of his head sheepishly.

"But, if you don't mind me asking, how are you gonna stop that drill all by yourself?" Naruto chuckled.

"Oh you'll see."

General Sung threw in his two copper pieces. "Oh indeed you'll see! Master Uzumaki in action is truly a sight to behold. He's been a magnificent help since he arrived here."

Naruto laughed. "You flatter me general." He took a few steps forward before crouching down on one knee facing the drill. He glanced over his shoulder at Aang before commenting. "I've been looking for you and your group, by the way. There's something I believe a past life of yours could help me with."

With that, he gathered an enormous amount of chakra into his legs and lept as high as he could towards the drill. Ignoring the amazed cry of Sokka below he gathered swirling chakra into his right hand as he arced lazily through the sky toward where the drill bit met the rest of the machine. By the time he arrived an Odama Rasengan was ready in his hand and extended toward the base of the drill bit; the weakest part of the drill's external structure.

An ear-shattering screech filled the air as Rasengan met drill, and a blinding explosion ensued as the swirling mass of chakra utterly decimated the metallic structure, completely separating the drill bit from the machine behind it. Shrapnel filled the air as Naruto quickly Shunshinned away to the base of the wall unscathed.

He dusted his cloak off before smiling at his handiwork. He turned and dashed all the way up the wall before jumping over the top of it and landing in a crouch in front of the gaang, arm extended behind him, and a shit-eating grin on his face. _'Damn I look cool.'_

Sokka was the first to shake the stunned expression of his face and speak. "How... What was... But you... and that... aaagh!"

Naruto stood up chuckling and put a hand on Sokka's shoulder. "Take a few deep breaths man, then ask your question again." The grin never left his face.

"That was incredible!" Exclaimed Katara. "The most amazing thing I've ever seen! How did you do that!"

Toph chimed in. "I couldn't see you while you were in the air, but I'm also pretty curious how you made that huge hunk of metal just blow up."

Aang had only one thing to say. "Whoa..."

"I told you we didn't need help." Chimed general Sung smugly.

Naruto took a few steps away from the gaang. "Well, I'm starved. Let's get some lunch, and I can answer all your questions while we eat."

Sokka was instantly alert at the mention of food. "Well, sounds good to me! Let's go guys."

xxxxxxxxxx

The gaang watched in stunned silence as Naruto _inhaled_ vast amounts of a noodly broth none of them had come across before. General Sung had led them to the soldier's mess hall atop the wall, where at least twenty bowls of the stuff had been waiting for him on a table, steaming. He instantly tucked in without saying anything and had been devouring non-stop since.

"So... Naruto, was it?" Katara hesitantly began.

"Mmph." Naruto acknowledged through his noodles. Katara continued. "Well, Aang introduced himself, but the rest of us never got a chance. I'm Katara." She gestured to herself. "And this is my brother Sokka."

Naruto slurped the broth from the bottom of his current bowl before slamming it down. He saluted them with two fingers. "Nice to meet ya'!" He immediately tore into his next bowl.

"And I thought I ate a lot." Sokka commented.

"And this is Toph." Katara finished her introduction. Naruto looked up and gave her a noodle-filled smile and an "Mmph!" before finishing the bowl. He reached for the next one, only to find he had just finished the last one.

"Oh... It's gone..." He whispered wistfully with a lone tear dripping from his eye.

"I... didn't think it was humanly possible to eat that much." Aang said.

Naruto waved him off. "Bah! I get that all the time. Alrighty then, question time. What do you guys want to know?"

Aang spoke up first. "How did you jump that high? And what was that glowing ball of energy in your hand?"

Naruto stroked his chin. "It's complicated. I'm not a bender per se, what I am is called a shinobi."

"Shin-what-now?" Sokka chimed.

"Shinobi." Naruto confirmed. "It means that I don't manipulate the elements, at least not directly like a bender does, but I shape my own internal energies to manipulate myself and the world around me. We shinobi call this internal energy 'chakra'. I channeled my chakra into my legs to boost how high I can jump, then I externalized pure chakra into the palm of my hand and spun it really fast in a lot of different directions, creating that glowing orb you saw. That attack is called 'Rasengan' by the way."

"That's incredible." gushed Katara. "How come we've never heard of shinobi before, if they're so powerful?"

Naruto turned melancholy. "As far as I know, I'm the only one in the world right now."

Katara covered her mouth with her hands. "I'm sorry, I didn't know - "

"It's alright." Naruto interrupted. "It's not quite what you think."

"How so?" Toph spoke up for the first time.

"It's actually why I need your help." He turned to Aang. "I don't know if I'm from the far future, the distant past, or another dimension entirely, but whatever the case may be, this world is completely unfamiliar to me. I wound up trapped in this world almost a year ago now, and after a lot of fruitless searching for answers about where and when I am in relation to my own home, I decided to seek out the Avatar. I thought maybe you, or a past life of yours, might know something about my home."

"Whoa whoa wait just a second - back up!" Sokka exclaimed. "You actually expect us to believe that! That's ridiculous!"

Naruto sent him a flat look. "More ridiculous than one person blowing up an entire gigantic metal drill by himself with one blow?"

"He has a point." Toph chimed. "Besides, I can feel when people are lying. There's a physical reaction when somebody lies. He's telling the truth – or he at least thinks he's telling the truth."

"I believe him." Aang added. "I've never heard of a shinobi before, and I was around a hundred years ago."

"I realize it all sounds a little outlandish." Naruto assented. "But it's true. Besides, what motive could I have for lying to you?"

Sokka grunted. "Points taken."

"Well I don't know how much help we'll actually be." Katara said softly, rubbing her arm.

"You see, I don't exactly have control of the Avatar state," Aang explained. "and I've never really summoned any of my past lives to talk to. They sort of just come to me when they have something to talk to me about."

"I see." Naruto stroked his chin again. "Well, I hate to ask, but could I travel with you then? I could be of use to you guys; and if I stick around with you I have a better chance of getting some useful information about my home."

Aang grinned. "Sure! I don't have a problem with that." He turned to the rest of the gaang. "any of you have an objection?"

"I don't know." Sokka said suspiciously. "Did he fill out an application to join Team Avatar?"

"Sokka!" cried Katara, smacking him on the back of the head. She turned to Naruto. "I have no problem with it. You seem like a nice guy, we'd be happy to lend a hand." She smiled at him.

Toph waved a hand around lazily. "Sure, he seems fine to me."

"Well, it's settled then." Sokka stated in his most 'official' voice. "Welcome to team Avatar."

xxxxxxxxxx

**A/N:** I'm pretty new to writing, and this is my first fanfiction story, as well as the first story I've posted somewhere it can receive public criticism. I'm not asking for 'gentle' reviews though, quite the opposite. If you're kind enough to take the time, I'd love for you to pick my writing apart and tell me what I could have done better. Thanks!

- Simon Riley


	2. Chapter 2

**A/N:** I'm sorry if at first this seems like just a re-telling of Canon, but it's necessary for the direction the story is going. By the end of this chapter you'll start to see some major divergence.

xxxxxxxxxx

"What are those lines on your face?"

"Birthmarks. Had 'em since I was born."

"Why is your hair... yellow?"

"It's called 'blonde'. It's not that uncommon a color where I'm from."

"How did you run _up_ the wall?"

"It's another chakra technique. I can also walk on water."

"Really? That's cool. What was tha-"

"Sokka! Enough questions." Katara batted him upside the head. "You've been badgering him non-stop since we got on the train! I'm sure he's sick of it. _I'm_ sick of it."

Sokka looked indignant. "Hey, you guys are the ones who let him into Team Avatar without even conducting a formal interview."

"You let _me_ on without an interview." Toph commented

Naruto laughed. "It's alright, Katara. I don't mind. I already said you guys can ask me as many questions as you like."

"Well, I've got one." Aang spoke up. "This chakra stuff... how do you get it? Like, is it in everybody? Or do just shinobi have it?"

"Oh, all humans – and animals too for that matter – have chakra. It's required for life. Shinobi are trained to tap into it though. It takes many years of hard work; I started my training when I was seven."

Aang looked thoughtful for a moment. "So, if everybody has chakra, how come no one here has learned to use it?"

Naruto grinned. "You have. You just don't realize it. It's a little complicated, so bear with me for a minute. Shinobi can use chakra techniques called ninjutsu to manipulate the elements, almost like benders, but with more restrictions. We have to actively turn the chakra in our bodies into elemental chakra of the element we want to manipulate, then shape that elemental chakra into a technique. I can demonstrate later if you like. However, the chakra in a bender's body is already elemental chakra.

For example, if I wanted to perform... say... a water technique, I'd have to first change the 'regular' chakra in my body into 'water' chakra. Then I'd have to shape that 'water' chakra into a technique and launch it. To perform another water technique, I'd have to repeat the whole process over again. However, the chakra in Katara's body is _already_ 'water' chakra, and she can continually shape it into one technique after the next using nothing but the fluid motions of her body, no pun intended. Get it?"

"Whoa... I think so. That's really cool. So does that mean you have control – or at least some control – over all the elements like me?"

Naruto nodded. "I know a few basic jutsu from each element, but I'm most proficient with wind and lightning. Usually I don't use elemental techniques though, except when I make a Rasengan out of elemental chakra."

Toph spoke up. "Wait, so does that mean that any bender could – in theory – learn more than one element if they were taught how to change the nature of the chakra in their body?"

"I just love how none of you are questioning anything he says." Sokka interjected. Naruto ignored him.

"Unfortunately no. The advantage of regular chakra is that you can change it's elemental nature. Chakra that has already been given an elemental nature cannot be changed from that nature, or used for non-elemental techniques. I honestly have no idea how _your_ chakra works-" he pointed at Aang. "-but that's how everyone else's works."

Naruto turned to Sokka smirking. "If you want, I could probably teach _you_ a few basic techniques that can be performed with regular chakra. That might cure your doubts."

Sokka scratched his chin. He did like the idea of learning how to blow up huge metal things and run on walls.

"Well, you did promise you'd be useful to us. A little training couldn't hurt."

"Why couldn't you teach him some elemental techniques?" Katara asked.

Naruto turned serious. "Elemental techniques take way more chakra than a newbie can safely access. If you try to shape elemental chakra before you have some experience under your belt, you'll likely kill yourself."

Sokka blanched. "Maybe it's not such a good idea after all..."

Naruto laughed out loud and gave him a hearty slap on the back. "I wouldn't teach you anything risky like that. I'm talking about the basics – the kind of basics a class full of eight-year-olds can do. That doesn't mean they're not useful techniques, mind you. The basics are the basics for a reason."

His skin returned to a healthy shade. "Well, I guess that's fine then."

Katara decided to change topics. "So Naruto, have you been inside Ba Sing Se yet?"

He shook his head. "Nope. Just on the wall. General Sung needed a hand when I arrived, so I just hung out there 'till you guys showed up. I'd learned that Princess Azula was tracking you, and it was easier to follow her than to follow you – I figured she'd lead me right to you. She came to Ba Sing Se, so I did as well."

"Wait, Azula's here? You mean outside the wall, not inside it, right?" Sokka said nervously.

"Yes." Naruto confirmed with a smirk. "She was actually in command of the drill I blew up. I'll bet she's pissed.

xxxxxxxxxx

Princess Azula was pissed. Downright furious, in fact. She had, after all, just witnessed the most powerful war machine ever created by the Fire Nation destroyed in one blow. She drummed her fingers agitatedly and let out a huff.

All around her, fire nation soldiers scurried frantically to strengthen the defenses of their little war camp. After such a devastating defeat, it would be the perfect time for an earth-bender counter-attack.

"Who _was_ that?" she absently asked out loud. Mai stopped twirling her knife to answer.

"How should we know? None of _us_ have ever seen him before."

Ty Lee chimed in. "Yeah, I'd remember someone with that hair-color. His aura was weird too, even from a distance. It felt... I'm not exactly sure how to describe how it felt but I'd definitely have recognized him if I'd met him before."

Azula's frown became more pronounced. "We'll have to be wary of him. Someone possessing that level of power is not to be taken lightly."

"Maybe he's a spirit!" Ty Lee squealed. "The Avatar might have summoned him to unleash that crazy powerful spirit attack!"

"Somehow I doubt that." Mai drawled. "The spirits don't like to be ordered around."

"Maybe one owed him a favor." Ty Lee countered, hands on hips.

xxxxxxxxxx

"I can't believe we finally made it to Ba Sing Se in one piece." Declared Katara cheerfully.

"Hey don't jinx it!" Sokka cried indignantly. "We could still be attacked by some giant exploding Fire Nation spoon! Or find out the city's been submerged in an ocean of killer shrimp!"

"You been hitting the cactus juice again?" Toph deadpanned.

"Mmmmm... Seafood..." Sighed Naruto dreamily.

"I'm just saying, weird stuff happens to us." At that moment an overweight man sucking on a corn cob sat down between him and Toph.

"See?" Sokka looked at Toph smugly around the man's large belly.

Katara noticed a melancholy look appear on Aang's face and decided to comfort him. "Don't worry, Aang. We'll find Appa for sure."

"It's such a big city." He countered dejectedly.

Sokka added his two copper pieces. "He's a GIANT bison, where could someone possibly hide him?"

The train crossed through the inner wall, revealing Ba Sing Se in all it's glory.

"Oh." Sokka meekly admitted.

"I could probably help you with finding him. I have some pretty good sensory abilities."

Aang's attention was instantly on Naruto.

"You do? How? What are they?"

Naruto smiled. "I'm what's called a Sage, a shinobi with the ability to pull the energy of nature into himself. When I do that, I can sense all the living things for a long ways around. I can do that to help you find him."

Aang smiled a million watts. "Really! That's awesome! We'll find Appa in no time now!"

The train arrived at the station in the upper ring of the city.

"Ahhh, back in the city." declared Toph with fake enthusiasm.

"What's wrong, it's amazing!" declared Sokka.

"Just a bunch of walls and rules." Countered Toph.

"But-" Naruto interjected "-rules can be fun when you break them. I once lead the ANBU, the police force of my hometown, on a three hour long chase all over the village, dropping paint bombs on them the whole time."

Toph perked up a bit. "Sounds fun. Let's have a go at that together sometime."

Just then, a lady approached them. She was dressed in formal clothing, had long black hair, and had an overly large smile on her face. Naruto didn't like her immediately.

"Hello! My Name is Ju Dee. I have been given the great honor of showing the Avatar around Ba Sing Se. You must be Sokka, Katara, Toph, and Naruto. Welcome to our wonderful city. Shall we get started?"

Naruto narrowed his eyes. She may have had more social tact than Danzo's lackeys, but he recognized that fake smile and the brainwashed look in her eyes. He already knew they shouldn't even bother with this woman.

"Yes." Sokka began seriously. "We have information about the Fire Nation that we need to deliver to the Earth King immediately."

"Great!" Agreed Ju Dee. "Let's begin our tour, then I'll show you to your new home here. I think you'll like it." She turned and began to walk away.

Sokka looked flabbergasted. "Look, maybe you didn't hear me the first time, but we need to get this information to the king. It's very important."

"You're in Ba Sing Se now." she replied with the same creepy smile. "Everyone is safe here." she continued to lead them towards a carriage.

Naruto put a hand on Sokka's shoulder and whispered to him. "Don't bother with her. I know her type. Just let her be our tour guide for the day, then we'll find a way to see the Earth King on our own."

Sokka gave him a serious look, then nodded. "If you're sure."

What followed was a long tour of all three rings of the city. Naruto didn't like it all one bit. The poor, middle, and upper castes were entirely seperated, and not allowed to mingle. He watched street rats like he used to be running amok in the lower ring, and the upper ring snobs that ignored their plight. He silently promised to do what he could for the city, should the chance arise.

He also took careful notice when they passed what Ju Dee said were Dai Li agents. When she described them as 'protectors of Ba Sing Se's cultural heritage', he instantly knew they were a group to watch out for. They just screamed 'secret police'.

At last they arrived at a comfy looking building in the upper ring.

"Here we are! Your new home. I'm sure you'll be very comfortable here."

A runner approached Ju Dee and handed her a scroll, which she quickly read. "More good news! Your request to see the Earth King is being processed, and should be put through in about a month. Much more quickly than usual."

"A month!" cried Sokka, appalled.

"Six to eight weeks, actually." She replied cheerfully. "Let's go inside." She quickly stepped through the doors of the upper-class house. "Isn't it nice? I think you'll really enjoy it here."

Sokka wasn't ready to give up. "I think we'd enjoy it more if we weren't staying so long. Can't we see the Earth-King any-" "Sokka, hold on a second." Naruto interrupted. He turned to Ju Dee.

"A moment of privacy, please?"

Ju Dee suddenly looked nervous. It was hardly noticeable, but to a trained shinobi the flicker of emotion on her face was more than enough.

"But you are still new here. Leaving you alone would make me a bad ho-" "Now." Naruto declared with thunder in his voice, the expression on his face now threatening. This time Ju Dee's nervousness became plain on her face.

"It'll only be a moment. Then you may come back." Naruto continued in the same sinister tone. Ju Dee blanched.

"V- very well. I'll be waiting outside." She quickly excused herself.

"Woohoo!" cheered Toph. "You _have_ to teach me that voice! She almost needed a new pair of underwear!"

Naruto chuckled. "I don't like scaring people like that, it doesn't really fit with my personality, ya' know? But sometimes you just can't afford to take no for an answer."

"Evidently not." Sokka agreed.

"So what was that about?" Katara asked.

Naruto rolled his shoulders. "We need to come up with a plan of attack. Ju Dee is obviously under orders from some higher power to keep us contained. Whether it's the Earth King, or some other person of authority, it doesn't really matter at this point. Keep in mind our two objectives in this city. One:-" He rose his right index finger "-is to find and recover Appa. Two:-" He rose his middle finger. "-is to convince the Earth King to buy into Sokka's invasion plan."

Naruto began to pace as he lectured.

"We need to find the most efficient way to accomplish these objectives. I'll stay here and use my Sage Mode to try and track down Appa. You go with Ju Dee – there's no way she'll leave you alone – and ask around the city for leads on him. But while you're doing that, work on Ju Dee a bit. See if you can figure out who she reports to, or any other useful information that might help us figure out why we're being kept from the Earth King. The Avatar is an important figure – even the Earth King _should_ have time to meet with him almost immediately."

He stopped pacing, and gave them all a serious look.

"When you guys get back tonight, I'll follow her – make sure you stay out until it's dark, it'll be easier to stay hidden. If any of you think you're stealthy enough, you can come too. We'll see where she goes, what she does, and figure out who exactly we're up against. We'll plan our next move after we know more. That sound good to you?"

"Wow. You've got a pretty strategic mind." Aang commented. Naruto shrugged.

"Eh, you can't really help but pick up a bit of strategic thinking when you're a shinobi. In my home, having a solid plan instead of just winging it is the difference between life and death."

"Well, I don't remember electing you leader, but I like your plan." Sokka assented. "Let's go with it."

"You're just jealous he actually _has_ a plan Sokka." Katara jabbed.

"Whatever. Lets go." Sokka turned and marched toward the door, quickly followed by all but Naruto.

"Wait a second, Toph, there's something I forgot." Naruto called. Aforementioned girl turned to face him.

"What is it?"

"Keep an eye - or actually a foot – out for the Dai Li. Those guys gave off a bad vibe; and the way Ju Dee referred to them... I just don't like it. Be wary if they come close – and if they do come close see what you can find out about how they operate."

"Will do. But how did you know I see with my feet? I never told you that."

Naruto shrugged. "You're obviously blind, at the wall you said you 'couldn't see me while I was in the air', and I know you're an earth bender. I just put the pieces together."

She grinned. "Cool. I will keep a foot out. Two, actually."

They filed out the door. As soon as it shut, Naruto dropped to the floor in a meditative position. He frowned.

_'The natural energy here in the city is so diluted – and there are just _so_ many chakra signatures... This is going to take awhile.'_

xxxxxxxxxx

"Well, that was a total bust." Sokka declared as he threw open the doors.

Naruto was sitting on the floor in the exact same position as when they left.

"You're going to have to get a move on if you want to track her." Aang said hurriedly. "She's already leaving in a carriage.

Naruto stood up. "Right. Anyone coming with me?"

"Whoa! What's up with your eyes?" Katara exclaimed.

"I'm in Sage Mode. We'll talk about it later. I need to hurry."

"I'll come with you." Aang said quickly.

Naruto scooped up two black cloaks he'd lain out on the floor. He tossed one to Aang before quickly shedding his trench coat and putting the other on. "Wear this. It'll be easier to hide."

Aang quickly pulled it on as Naruto opened a window. "Let's go." He leapt out, and Aang followed.

It was easy enough to follow the carriage. It was slow moving, and they easily kept up leaping from roof to roof. Under cover of dark, not being seen was child's play.

The carriage arrived at a small door in the back of the royal palace, and Naruto quickly moved to the top of a building right next to it, Aang right behind him.

"Get ready. When Ju Dee goes inside we'll need to be right behind her, and completely silent." Aang grunted in acknowledgement.

Ju Dee emerged from the carriage, which immediately moved on. When She opened the large door, Naruto moved. Not waiting to see how Aang would go about following her, he leapt for the top of the door frame. Without making even the slightest sound, he caught the top of it. Letting his momentum carry his lower body forward, he swung through the door and landed his feet on the roof of what he instantly identified as a long, tall, dimly lit hallway. No one else was around.

_'This is just too easy.'_

He looked around for Aang, and saw him clinging to one of the decorative chandeliers that hung from the ceiling in intervals. They exchanged nods, before following her, Aang traveling from chandelier to chandelier and Naruto crawling on the ceiling.

Ju Dee took several turns before coming to a much narrower and smaller hallway with no more chandeliers. Thankfully, it was also darker, and their inky black cloaks were effective. Naruto stayed on the ceiling and Aang hugged a wall. It also helped that Ju Dee never once looked back.

At last she arrived at a small unassuming wooden door, which she entered without hesitation. From his spot on the ceiling Naruto made out an office, and he could see the legs of someone sitting in a chair in front of a fire place, but nothing else. After the door closed he dropped to the floor, and gestured for Aang to come up to the door with him.

Naruto pressed a finger to his lips, then put his ear to the door, channeling chakra to help him hear better.

"_Ju Dee"_ spoke a deep male voice. _"how were the Avatar and his companions?"_

"_They behaved almost exactly as you predicted. They were persistent about wanting to meet with the King, but were contented with searching for their lost bison. There was one though, who seemed suspicious. Naruto. He definitely doesn't trust me, and he stayed behind when I took the rest out looking for the bison. I don't know what he did during that time."_

There was a pause. _"Continue to lead them on their wild goose chase for now. I'll have the Dai Li keep a closer eye on them. Especially Naruto. That is all, you are dismissed."_

"_Yes, Long Feng, Sir."_

Footsteps approached the door.

Naruto looked at Aang, who was clearly shocked by what he just heard, his eyes wide. He clapped a hand over his mouth to prevent him from crying out, then lept to the ceiling hanging onto him just in time for the door to open.

Ju Dee walked out, then down the hallway the way she came. Naruto soundlessly dropped to the floor, then set Aang down.

Naruto whispered hurriedly. "It seems that whoever is behind that door is the head of, or at least an authority within, the Dai Li. He both has Appa, and wants to keep us from the Earth King. We'll capture him silently, no one can know we took him, then we'll interrogate him to find out what we need to know. Stay here and stay silent. I'll be right back."

Not giving Aang a chance to reply, he formed a few handsigns and intoned the name of his jutsu. _'Doton: Shinju Zanshu no Jutsu' _he vanished into the stone floor.

Aang shook his head to clear off his shock, and pressed his ear to the door again. A few moments passed, then he heard the beginning of a cry of shock, quickly muffled. Naruto opened the door.

"All clear. Come in."

Aang stepped inside, and was greeted with the sight of a man – mostly bald but with a long pony tail – buried up to his neck in the stone floor. He was gagged. Naruto quickly stepped over to his desk and began pulling files.

"What did you do?" Aang asked.

"An earth-style jutsu. To capture him. I present to you Long Feng, head of the Dai Li, and our prisoner."

Said man was glaring daggers.

Naruto whistled at the document he was reading. "Wow. Looks like this guy has the whole city under his thumb. He's basically King. King Kuei is a puppet. With these documents, we don't even need to interrogate him."

He pulled out a scroll and brush, and began sealing all the documents away.

Long Feng began grunting through his gag.

"Wait." Aang said. "I don't think it's right to go to these extremes."

Naruto pointed at Long Feng. "He went to extremes first. Besides, we need to get Appa and the Earth King's support. Stay focused on our objectives. This man is the only obstacle to both of those objectives. Appa is being held in a secret facility beneath Lake Laogai. This man put him there. He's trying to keep us from seeing the Earth King and ending this war just to maintain control of the city. Evil men need to be removed from power – by force if necessary.

With him in custody and these documents as proof, we can reveal to the King how he's been used, and restore his rightful powers. He'll be grateful to us for revealing the conspiracy to him, which increases our odds of getting him on board with the invasion plan."

Aang looked down. "I suppose you're right." he sounded defeated.

Naruto strode over to Long Feng and crouched down. "Time to take a nap." He jabbed a pressure point on the man's neck, knocking him unconscious. He pulled him from the floor, and Aang mended the hole.

Naruto slung Long Feng over his shoulder.

"Time to go."

xxxxxxxxxx

"That's right young man! Your life is about to change for the better!"

"I'll try to contain my joy." Zuko said bitterly. This was _not_ the life he wanted.

He stepped outside to try and relax. Two people walking by caught his attention.

"No way! The _Avatar_ visited _your_ pet shop?"

"Yep." The man boasted proudly. "He was looking for his lost Sky Bison... I thought they were extinct. If the Avatar says one's left though, it's gotta be true."

xxxxxxxxxx

**A/N: **I'm going to try and preemptively answer a question. Zuko's timeline is obviously not lined up with the gaang's the same way it is in Canon; neither is Jet's. Jet has already been captured and brainwashed, but not yet sent out to mislead Aang. He'll be showing up next chapter. Other than that, things went just as they did in Canon for Zuko and Jet.

I'm trying to keep it interesting by not moving too slowly, but I feel like I may have paced things too fast in the process. I didn't really leave much time in there for some development of Naruto's relationships with the members of the gaang. I thought things made most sense this way though - Naruto is a shinobi prone to action. He's not one to spend much time sitting around like the gaang did in Canon. With him on their side things would have definitely gone faster in Ba Sing Se, one way or another. I'd like to hear _your _opinions if you'd be kind enough to leave a review. =)

- SimonRiley


	3. Chapter 3

**A/N:** **READ THIS:** I am discontinuing this story, and doing a re-write. If you're interested enough to keep reading, here's why.

Post-war Naruto is way too overpowered for the Avatar universe. Even avatar state Aang would be demolished if Naruto got serious. Heck, Naruto could probably singlehandedly destroy any nation he wanted to. I thought I had a good outline written up for this story, but when I took a step back and looked at it, I realized all it really was is _"Naruto blows through every conflict with his awesomeness and saves the world instead of Aang."_ I tried to write around that, but it never really felt right. I had to make Naruto way weaker than we know him to be, and that's just depressing.

I will be working on a re-write with the same premise, except Naruto gets dropped into the Avatar-verse much earlier in his development, so that he's not too overpowered. If you're interested, check it out when I post it.

I finished writing the next chapter, however, so I decided to post it for shits and giggles. There will be no more after this. Here you go.

xxxxxxxxxx

The Dai Li is a powerful agent within Ba Sing Se; the most powerful. They have but one weakness: numbers. As skilled as each and every individual agent is, they number few in comparison to the Army's and Royal Guard's presences within the city. Because of this every on-duty agent is always busy, and security details can't always be kept tight. To make up for this, a 'check in' system was established.

At discrete locations within the city, individuals in the employ of the Dai Li keep watch for any agent deployed in their sector who fails to check in at predetermined times. These individuals can be anybody – from shopkeepers to street performers. If an agent fails to check in, the alarm is raised.

So, when Long Feng failed to meet his last check in for the night, an old drunk politician singing love songs to pretty women took notice. He scurried off to raise the alarm.

xxxxxxxxxx

"Hey guys, what did you find ou... who the hell is that?" Sokka screeched.

Naruto unceremoniously dropped his cargo onto the floor.

"Long Feng, head of the Dai Li." he deadpanned.

"You kidnapped the head of the Dai Li!" Katara shrieked. "Why!"

"He's got Appa, and he's the one trying to prevent us from seeing the Earth King. I found some very interesting documents and records in his office – from the looks of things he's got the entire city under his thumb. He's got more power than the Earth King; not that the Earth King knows that."

Toph Whistled. "Wow. Glad we nipped that one in the bud. Imagine how much trouble this guy could've caused us."

Sokka was still outraged. "I thought you said we'd plan our next move after getting more information!"

Naruto had the decency to look apologetic. "Sorry about that, but I saw an opportunity too good to pass up. We found out that this man was the source of all our problems, and we were presented with the perfect opportunity to nab him."

Aang spoke up in support. "Yeah, we know exactly where Appa is now, and we can go see the Earth King as soon as we get him."

Toph concurred. "I'm _all_ for getting our time in this city over and done with as fast as possible. I like busting down doors and breaking bones; it gets the job done faster than twiddling our thumbs."

Even Katara seemed on board. "It seems a little extreme to me... but with a guy like that blocking our way I guess it only makes sense to use force to push through."

Sokka seemed exasperated. "_Fine._ But just so we're clear, I don't like how you just went ahead and kidnapped the head of a powerful organization without even consulting the rest of us first."

Naruto gave him a serious nod. "Duly noted. I'll do my best to make sure and talk to all of you about future important decisions before making them."

That seemed to appease Sokka. "That's all I ask."

"So where are they holding Appa?" Katara asked.

"In a secret facility beneath Lake Laogai, outside the inner wall." Aang responded. "We should go rescue him now!"

Naruto threw in his two copper pieces. "It would be good to strike now – while the Dai Li is leaderless and prone to falling into disarray."

"What are we waiting around for? Let's go!" cried Toph enthusiastically. "Wait a sec... there are two people coming up to our door."

"Who?" asked Aang.

"Don't know; they're not Dai Li though."

A knock sounded on the door and Katara cautiously opened it. Her eyes widened in shock.

"Long Shot? Smellerbee?"

The tomboy looked up at her with somber eyes. "We need your help."

xxxxxxxxxx

Commander Morioka was next after Long Feng in the Dai Li's simple ranking system. Right now agents were beginning to scour the city for signs of him. Commander Morioka himself was standing in Long Feng's office – eyes carefully scanning for anything out of place.

Long Feng's record box was missing, but that wasn't out of the ordinary. He always took it home and locked it in his safe – older documents were stored in an archive beneath Lake Laogai. However, Long Feng was not at home and his safe was empty. That _was_ out of the ordinary.

Who could have the means and the motive to abduct Long Feng? Unless there was a traitor in the Dai Li, there was no one. A mole hunt, however, would have to wait until after a preliminary search.

Commander Morioka rubbed his chin in thought. What recent anomalous events could be linked to his disappearance? Even events that seemed to have nothing to do with it were worth investigating. Morioka snapped his rock covered fingers – don't ask how – as a thought occurred to him. It would probably prove fruitless, but any lead was worth chasing.

He gestured to the Captain standing behind him. "Send a pair of agents to the Avatar's new residence."

xxxxxxxxxx

"Jet... He really reformed?" Katara sounded skeptical, but hopeful.

"Yes!" Smellerbee insisted. "He became a totally different person after you guys left! He realized what he was doing, and spent three days sobbing in shame. He left all the rest of the gang behind but us... we wouldn't leave him."

"And you came to Ba Sing Se for a new start. Jet got paranoid and stirred up trouble, and the Dai Li capped him." Sokka finished.

"Yeah." Smellerbee said tiredly.

Longshot – as usual – hadn't spoken a word. He looked at them with sorrowful pleading eyes.

"Well -" Naruto began. "- I say why not? We're already going to rescue Appa – why not get Jet too? He sounds like a decent guy to me, even if he was loopy in the head until just a little while ago."

Katara clenched her fists. "Let's do it."

"I'm in." Chimed Sokka.

Toph punched her open palm with a fist. "Let's go have some fun."

Tears came from Smellerbee's eyes, but she quickly wiped them away. "T-thank you. I don't know what to say."

Katara put her hand on the younger girl's shoulder and gave her a confident smirk. "Let's go."

"Waaaiiit a second!" Cried Sokka. "What are we gonna do with him?" He pointed to the unconscious Long Feng. "We should at least tie him up or something."

Naruto smirked. "It's alright. I got this." Three new Narutos poofed into existence, and everybody screamed. Except Toph – she just jumped a little.

"How... What... but you..." Sokka stammered.

Naruto clapped a hand on his shoulder. "They're called Shadow Clones. I'll tell you more about them later. For now we need to a get a move on."

xxxxxxxxxx

It was easy enough making it to the inner wall speedily – but the gates were closed at night, and a rock elevator would be too noisy. This wasn't a problem for Naruto and Aang, but the rest of them weren't so lucky.

Naruto eyed their little group carefully. "Right." Three clones popped into existence. Everyone jumped, but no one cried out this time. "Everyone grab a clone and hang on. I'll get you over the wall. Aang, you take somebody too."

When nobody moved, the Narutos grumbled. They each picked up a stunned person and ran up the wall, leaving just Aang with Toph. Aang blinked. "You see that too, right Toph?"

She nodded. "Yeah. Sort of." She turned green. "I guess you're my ride over the wall then, huh?"

Aang nodded somberly. "Yeah."

xxxxxxxxxx

They reached the lake without incident; except Toph refused to be carried over the next wall. She tunneled under it instead, as quietly as she could.

When they reached the lake it took all of two seconds for Toph to find them their entrance, an underwater tunnel hidden by Earthbending. Seven pairs of eyes stared warily down the hatch.

"Right. Who wants to go down the creepy hole first?" Sokka asked. Naruto jumped down without responding, not even catching the ladder. Chakra-powered legs absorbed the impact of his fall soundlessly. He looked and found himself in a some kind of antechamber. All it contained was the ladder to the hatch and a large steel door.

"All clear!" he called to his companions. They soon joined him. Toph stomped a few times. "It's hard to see long distances down here. The water surrounding these caves makes things seem all... echoey."

"Echoey?" Aang questioned.

"Yeah echoey. I can see just fine up close, but my vision gets all echoey when I try to look too far away. We'll have to search for Appa and Jet the old fashioned way."

"Right." Sokka started. "Well, can you at least tell us what's right past this door? I don't want things to get ambushy."

"Relax, it's all clear."

Naruto slowly turned the locking wheel on the door, getting it open with barely a squeak. It revealed a long ominous hallway with many branches. Everyone, now completely silent, began to creep down the hallway single file – Naruto, Toph, Aang, Katara, Sokka, Smellerbee, and Longshot.

Naruto quietly pointed out a room full of new Ju Dee drones. "See, knew she was trouble. We'll have to get these poor women out of here too."

They crept a bit further before Toph stopped them. "I think I feel a few holding cells at the end of that hallway. I don't know what Jet feels like, so I can't say for sure if he's there, but I think it's worth our time to look."

"Great." Sokka whispered back. "Lead on." he pointed accusingly at Naruto. "There wasn't even a map with all those top secret documents?"

Naruto shrugged. "They were all records of the Dai Li's movements. No technical documents, I'm afraid."

The corridor was much the same as the main one, just a tad narrower, and lined with doors.

"_All _these doors lead to a cell," Toph shared. "but only a few at the end have anyone in them."

"Jet has a thin, lithe build. He's pretty light, he can't weigh more than 70 kilograms." Smellerbee described. "does that help?"

"Yeah, that's great." Toph replied. "Try that cell." She pointed to an indiscriminate door. Naruto grabbed the handle, took a deep breath, and yanked as hard as he could. The latch snapped and the door slid open.

"Jet!" cried Smellerbee. She rushed into the cell, where Jet lay battered on his back, unconscious. Smellerbee smacked his cheeks several times. "Jet, wake up! Come on!"

"Shush!" scolded Sokka. "We don't want every Dai Li agent in here to come running."

"I have some smelling salts." Naruto quickly offered, producing a small vial. He held them under Jet's nose, and he awoke with a jolt.

"What the hell?" He sat up quickly, introducing his nose to Naruto's forehead in the process. "Gaaaaah!" Naruto clamped a hand over his mouth before he could emit any more noise.

"Calm down. We're here to rescue you. Jet and Smellerbee are with me. We need you to be quiet though." Longshot was already outside the cell door with an arrow nocked, facing the way they came.

Jet met Naruto's eyes and nodded as well as he could. Naruto removed his hand. Smellerbee was instantly hugging him, doing her best to squeeze him back into unconsciousness.

"What happened?" He asked no one in particular "How did I get here?"

"The Dai Li dragged you off. We were so worried about you." Smellerbee explained, sniffling.

"What are you talking about? The last time I saw you guys is when I left for the city. I've been living here peacefully for months now."

Before anyone could respond to Jet's outlandish claim, Naruto startled. "The Dai Li found out it was us. I don't know how. They ambushed my clones and got Long Feng back. We need to get out of here."

"Not without Appa." declared Aang.

Toph stomped the ground as hard as she could. She waited a moment, then tried again. "I still can't see far enough to pinpoint him. I'm sorry."

"I want to know what's going on!" demanded Jet. Naruto rounded on him. "We'll deal with details later, there's no time now. All you need to know right now is that the Dai Li agents are bad guys. Do you need a weapon?"

Jet looked taken aback, but decided to just accept things for now. "I could use a weapon. I don't know what happened to my swords and armor."

Naruto handed him two kunai knives, then turned to Aang. "We do _not_ want to get pinned down in these caves."

"I'm not leaving without Appa." Aang insisted.

Naruto caved. "Fine." he closed his eyes, and when they re-opened they were amber. The horizontal pupils and red pigmentation around his eyes marked him a sage. His brow furrowed in concentration for a moment.

"They're already moving him. Two agents have him and are taking him above... wait a second, those guys aren't agents! They're firebenders! They have fire chakra flowing through them!"

"What!" cried Aang.

"How is that possible!" Katara asked.

"Doesn't matter right now." Sokka took charge. "We just need to get to the surface as fast as possible and head them off."

Aang was already running back down the hallway. "Let's go!" he yelled.

"Well I guess we've forsaken stealth!" Naruto called back as he took off after Aang, closely followed by everyone else.

Several agents were now waiting for them in the main hallway, alerted to their presence. The front two fired their rock gloves, intent on pinning Aang and Naruto – who were leading the pack.

Aang easily smashed the two fired at him with his staff and Naruto dodged the two aimed at him. He was quickly upon the two agents and they both received Sage powered fists to the gut, knocking them out cold. Toph leaped ahead of him and pinned another two agents to the walls with earthen handcuffs, leaving only one agent left. Katara bitch-slapped him with a water whip before he could react.

They had almost made it back to the ladder when at least ten other agents showed up behind them in hot pursuit. Naruto and Aang fell to the back of the group and faced the agents.

_'Fuuton: Daitoppa'_ Naruto cried while Aang unleashed a powerful gale of wind. The agents didn't stand a chance. In such a narrow hallway the rushing wind's power was intensified, and they were all viciously blasted backwards. The gaang all made it back into the antechamber, and Naruto slammed the door behind them. Toph braced it with an earthen slab.

xxxxxxxxxx

Long Feng was furious. He was furious at the Avatar and his crew for making a fool of him, and furious at himself for allowing himself to be made a fool of. He'd be sure to rid the city of the Avatar now. As soon as he'd been found he scrambled all of the Dai Li to converge on Lake Laogai. Those pitiful fools would never see the light of day again.


End file.
